import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    public TreeNode(int val) {
        this.val = val;
    }
}



public class Test_9_1 {


    //力扣：110. 平衡二叉树
    public boolean isBalanced(TreeNode root) {
        if(root == null) return true;
        //1. 分别求左右子树的高度
        int lH = getHeight(root.left);
        int rH = getHeight(root.right);
        //2. 如果 lH 或 rH 返回值为-1，代表左右子树的子树存在非平衡二叉树；若lH - rH 的绝对值大于1，也为非平衡二叉树
        if(lH == -1 || rH == -1 || Math.abs(lH - rH) >1) return false;
        return true;

    }
    private int getHeight(TreeNode root) {
        if(root == null) return 0;

        int leftHeight = getHeight(root.left);
        int rightHeight = getHeight(root.right);
        if(leftHeight == -1 || rightHeight == -1 || Math.abs(leftHeight - rightHeight) >1) {
            return -1;
        }else {
            return (leftHeight>rightHeight?leftHeight:rightHeight) + 1;
        }
    }



    //力扣：101. 对称二叉树
    public boolean isSymmetric(TreeNode root) {
        if(root == null) return true;
        boolean answer = isSymmetricChild(root.left, root.right);
        return answer;
    }
    private boolean isSymmetricChild(TreeNode leftTree, TreeNode rightTree) {
        if(leftTree == null && rightTree == null) return true;
        if(leftTree == null || rightTree == null) return false;

        if(leftTree.val == rightTree.val) {
            return isSymmetricChild(leftTree.left, rightTree.right)
                    && isSymmetricChild(leftTree.right, rightTree.left);
        }else {
            return false;
        }
    }



    //力扣：236. 二叉树的最近公共祖先
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if(root == null) return null;
        if(root == p || root == q) return root;

        TreeNode leftTree = lowestCommonAncestor(root.left, p, q);
        TreeNode rightTree = lowestCommonAncestor(root.right, p ,q);
        if(leftTree != null && rightTree != null) {
            return root;
        }else if(leftTree != null) {
            return leftTree;
        }else {
            return rightTree;
        }
    }



    //力扣：606. 根据二叉树创建字符串
    public String tree2str(TreeNode root) {
        StringBuilder str = new StringBuilder();
        StringBuilder ret = func(root, str);
        return ret.toString();
    }
    private StringBuilder func(TreeNode root, StringBuilder str) {
        if(root == null) return str;

        str.append(root.val);

        if(root.left != null) {
            str.append('(');
            func(root.left, str);
            str.append(')');
        }else {
            if(root.right != null) {
                str.append("()");
            }
        }

        if(root.right != null) {
            str.append('(');
            func(root.right, str);
            str.append(')');
        }
        return str;
    }




    //力扣：144. 二叉树的前序遍历
    //非递归实现
    public List<Integer> preorderTraversal(TreeNode root){
        List<Integer> ret = new ArrayList<>();
        if(root == null) return ret;

        Stack<TreeNode> stack = new Stack<>();
        TreeNode cur = root;
        TreeNode top = null;
        while(cur != null || !stack.empty()) {
            if(cur != null) {
                ret.add(cur.val);
                stack.push(cur);
                cur = cur.left;
            }else {
                top = stack.pop();
                cur = top.right;
            }
        }
        return ret;
    }



    //力扣：94. 二叉树的中序遍历
    //非递归中序遍历
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> ret = new ArrayList<>();
        if(root == null) return ret;

        Stack<TreeNode> stack = new Stack<>();
        TreeNode cur = root;
        TreeNode top = null;
        while(cur != null || !stack.empty()) {
            if(cur != null) {
                stack.push(cur);
                cur = cur.left;
            }else {
                top = stack.pop();
                ret.add(top.val);
                cur = top.right;
            }
        }
        return ret;
    }



    //力扣：145. 二叉树的后序遍历
    //非递归实现
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> ret = new ArrayList<>();
        if(root == null) return ret;

        Stack<TreeNode> stack = new Stack<>();
        TreeNode cur = root;
        TreeNode top = null;
        TreeNode flag = null;
        while(cur != null || !stack.empty()) {
            if(cur != null) {
                stack.push(cur);
                cur = cur.left;
            }else {
                top = stack.peek();
                if(top.right == null || top.right == flag) {
                    top = stack.pop();
                    ret.add(top.val);
                    flag = top;
                }else {
                    cur = top.right;
                }
            }
        }
        return ret;
    }

}
